package com.zang.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 子集II
 * @author ZVerify
 * @since 2022/11/15 09:17
 * @see <a href="https://leetcode.cn/problems/subsets-ii/description/">...</a>
 **/
public class 子集II {
    // 最后结果
    List<List<Integer>> result = new ArrayList<>();
    // 返回结果
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        // 字典用于剪枝
        boolean[] mapInts = new boolean[nums.length];
        backtrack(nums,0,mapInts);
        return result;
    }

    private void backtrack(int[] nums, int startIndex,boolean[] map) {
        // 去重
        result.add(new ArrayList<>(list));

        // 终止
        if (nums.length == startIndex) return;

        for (int i = startIndex; i < nums.length; i++) {
            // 树层要去重
            if (i>0 && nums[i] == nums[i-1] && !map[i-1]) continue;
            map[i] = true;
            list.add(nums[i]);
            // 下一层
            backtrack(nums,i+1,map);
            // 回溯
            list.remove(list.size() - 1);
            map[i] = false;
        }
    }
}



